import java.util.ArrayList;
/**
 * Preflow Push algorithm that solves the Maxflow problem. 
 * 
 * Vertices have two data fields, name and data.
 * Name contains a string, data contains a string which indicates the height
 * and the excess flow in the vertex.
 * 
 * Edges have two data fields, name and data.
 * Name is null, data contains a string which indicates the flow and capacity
 * in the edge.
 * 
 * TCSS 543 Advanced Algorithms
 * University of Washington Tacoma
 * Professor D. Chinn
 * 
 * @author Sean Chung
 *
 */
public class PreflowPush {
  private SimpleGraph graph;
  private Vertex sink = null;
  private Vertex source = null;
  private ArrayList<Vertex> activeVertices = new ArrayList<Vertex>();
  
  public PreflowPush(SimpleGraph graph) {
    this.graph = graph;
  }
  
  /**
   * Initialize the starting flow of the graph.
   * 
   * All vertices but the source have a height and excess flow of 0 to start; 
   * the source node contains a height of the number of vertices in the graph
   * and an excess flow of 0.
   * 
   * All edges but the ones connected to source contain a capacity and flow of 0;
   * Edges coming from the source contain a capacity and a flow equal to capacity.
   */
  public void initialization() {
    for (Object v : graph.vertexList) {
      Vertex vertex = (Vertex) v;
      if (vertex.getName().equals("s")) { // Find the source.
        source = vertex;
        vertex.setData(graph.numVertices() + ",0");
      }
      else if (vertex.getName().equals("t")) { // Find the sink.
        vertex.setData("0,0");
        sink = vertex;
      }
      else {
        vertex.setData("0,0");
      }
    }
    
    for (Object e : graph.edgeList) {
      Edge edge = (Edge) e;
      
      double data = (Double) edge.getData();
      int capacity = (int) (data);
      Vertex v = edge.getFirstEndpoint();
      
      if (v.equals(source)) { // Find edges that come out of source.
        Vertex w = graph.opposite(v, edge);
        edge.setData(capacity + "," + capacity);
        setExcess(w,capacity); 
        activeVertices.add(w);
      }
      else {
        edge.setData(capacity + ",0");
      }
    }
  }
  
  /**
   * Find the max flow of the input graph. Uses a preflow push approach.
   * @return maximum flow of input graph
   */
  public int maxFlow() {
    initialization();
    int max = 0;
    while (!activeVertices.isEmpty()) { 
      Vertex v = activeVertices.get(0);
      if (getExcess(v) <= 0) {
        activeVertices.remove(v); // If vertex doesn't have excess flow remove.
      }
      else {
        preflowPush(v);
      }
    }
    
    // Add up the flow on edges going to sink. 
    // Would also work with edges coming from source.
    for (Object e : sink.incidentEdgeList) {
      Edge edge = (Edge) e;
      max += getFlow(edge);
    }
    return max;
  }
  
  /**
   * See if a push can be executed on the input vertex, if not do a relabel.
   * @param vertex the active vertex to look at
   */
  public void preflowPush(Vertex vertex) {
    for (Object e : vertex.incidentEdgeList) {
      Edge edge = (Edge) e;
      
      // Variables.
      int flowChange = 0;
      int flow = getFlow(edge);
      int excessV = getExcess(vertex);
      int capacity = getCapacity(edge);
      Vertex w = graph.opposite(vertex, edge);
      
      if (getHeight(vertex) > getHeight(w)) { 
        // Forward edge.
        if ((edge.getFirstEndpoint().equals(vertex))) {
          flowChange = Math.min(excessV, (capacity - flow));
          flowUpdate(edge, flow + flowChange);
        }
        // Backward edge.
        else if ((edge.getSecondEndpoint().equals(vertex))) {
          flowChange = Math.min(excessV, flow);
          flowUpdate(edge,flow - flowChange);
        }
      }
    }
    // Relabel if no pushable edges found.
    setHeight(vertex, getHeight(vertex) + 1);
  }
  
  /**
   * Update the flow while pushing.
   * @param e the edge that has flow pushed onto it
   * @param flow the flow being pushed
   */
  public void flowUpdate(Edge e, int flow) {
    Vertex v = e.getFirstEndpoint();
    Vertex w = e.getSecondEndpoint();
    
    int flowChange = flow - getFlow(e);
    int excessV = getExcess(v);
    int excessW = getExcess(w);
    
    setFlow(e,flow);
    setExcess(v, excessV - flowChange);
    setExcess(w, excessW + flowChange);
     
    checkVertex(v);
    checkVertex(w);
  }
  
  /**
   * Check if the vertex is qualified to be an active vertex. 
   * Vertex cannot be the source or sink, and must have an excess flow > 0.
   * @param v the vertex to check
   */
  public void checkVertex(Vertex v) {
    if ((!v.equals(source)) && (!v.equals(sink)) && (getExcess(v) > 0)) {
      activeVertices.add(v);
    }
  }
  
  /**
   * Returns the excess flow for a vertex
   * @param v the vertex to return an excess flow for
   * @return int value of excess flow
   */
  public int getExcess(Vertex v) {
    String[] data = ((String) v.getData()).split(",");
    return Integer.valueOf(data[1]);
  }
  
  /**
   * Returns the height value for a vertex
   * @param v the vertex to return a height for
   * @return int value of height
   */
  public int getHeight(Vertex v) {
    String[] data = ((String) v.getData()).split(",");
    return Integer.valueOf(data[0]);
  }
  
  /**
   * Sets the value of excess flow for a vertex
   * @param v the vertex to set the excess flow for
   * @param excess value to give the vertex for excess
   */
  public void setExcess(Vertex v, int excess) {
    v.setData(getHeight(v) + "," + excess);
  }
  
  /**
   * Set the value of height for a vertex.
   * @param v the vertex to set the height for
   * @param height value to give the vertex for height
   */
  public void setHeight(Vertex v, int height) {
    v.setData(height + "," + getExcess(v));
  }
  
  /**
   * Get the flow of an edge.
   * @param e the edge to get the flow from
   * @return int value of edges flow
   */
  public int getFlow(Edge e) {
    String[] data = ((String) e.getData()).split(",");
    return Integer.valueOf(data[1]);
  }
  
  /**
   * Get the capacity of an edge.
   * @param e the edge to get the capacity from
   * @return int value of capacity
   */
  public int getCapacity(Edge e) {
    String[] data = ((String) e.getData()).split(",");
    return Integer.valueOf(data[0]);
  }
  
  /**
   * Set the flow of an edge
   * @param e the edge to set the flow for
   * @param flow the flow value to set for edge
   */
  public void setFlow(Edge e, int flow) {
    e.setData(getCapacity(e) + "," + flow);
  }
  
  /**
   * Set the capacity for an edge
   * @param e the edge to set the capacity for
   * @param capacity the capacity value to set for edge
   */
  public void setCapacity(Edge e, int capacity) {
    e.setData(capacity + "," + getFlow(e));
  }
  
  @SuppressWarnings("static-access")
  public static void main(String[] args) {
    String graph1 = "/Users/Macky/Winter_2013/Algorithms/graphs/Fixed/first.txt";
    String graph2 = "/Users/Macky/Winter_2013/Algorithms/graphs/BipartiteGraph/g1.txt";
    String graph3 = "/Users/Macky/Winter_2013/Algorithms/graphs/BipartiteGraph/g2.txt";
    SimpleGraph graph = new SimpleGraph();
    
    GraphInput input = new GraphInput();
    input.LoadSimpleGraph(graph, graph1);
    
    PreflowPush flow = new PreflowPush(graph);
    System.out.println(flow.maxFlow());
  }
}